#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import Counter

class Solution:
    """
    @param nums: A list of integers
    @param k: An integer
    @return: The majority number
    """
    def majorityNumber(self, nums, k):
        # self.k = k

        self.counter = Counter()

        for ele in nums:
            if ele in self.counter or len(self.counter) < k-1:
                # 在槽里 或者 槽没有满
                self.counter[ele] += 1
            else:
                # 不在槽里: 并且槽满了, 并且和新元素都不同. 计数减1, 如果为0, 踢出.
                # NOTE: intuition 凑齐k个不同的数, 放到trash中, 不影响结果
                cancel_outs = []
                for slot in self.counter:
                    self.counter[slot] -= 1
                    if self.counter[slot] == 0:
                        cancel_outs.append(slot)

                for cancel in cancel_outs:
                    del self.counter[cancel]

        ret = self.check(list(self.counter), nums, k)
        if ret:
            return ret[0]

    def check(self, cands, nums, k):
        threshold = len(nums) / k
        counter = Counter()

        for ele in nums:
            if ele in cands:
                counter[ele] += 1

        ret = [cand for cand in counter if counter[cand] > threshold]
        return ret


def main():
    print("start main")

if __name__ == "__main__":
    main()
    s = Solution()
    s.majorityNumber([1,2,3, 1,2,3, 5, 2], 3)
